#include <malloc.h>
#include "myList.h"

//创建链表(无节点比较指针)
MyList *createMyList(void) {
    MyList *mlist = malloc(sizeof(MyList));
    mlist->first = mlist->last = NULL;
    mlist->count = 0;
    mlist->equal = NULL;
    return mlist;
}

//创建带节点比较指针的链表
MyList *createMySearchList(int(*equal)(LNTYPE a, LNTYPE b)) {
    MyList *mlist = createMyList();
    mlist->equal = equal;
    return mlist;
}

//释放链表
void freeMyList(MyList *list) {
    MyNode *p = list->first, *pp;
    while(p) {
        pp = p;
        p = p->next;
        free(pp);
    }
    free(list);
}

//释放链表节点数据都为malloc指针，一同释放
void freeMyListP(MyList *list) {
    MyNode *p = list->first, *pp;
    while(p) {
        pp = p;
        p = p->next;
        free((void*)pp->data);
        free(pp);
    }
    free(list);
}

//插入在尾部
void myListInsertDataAtLast(MyList* const list,  LNTYPE data) {
    MyNode *p;
    if(list->first) {
        p = list->first;
        while(p->next) {
            p = p->next;
        }
        p->next = malloc(sizeof(MyNode));
        p = p->next;
    }else {
        p = list->first = malloc(sizeof(MyNode));
    }
    p->data = data;
    p->next = NULL;
    list->last = p;
    list->count++;
}

//插入在首部
void myListInsertDataAtFirst(MyList * const list,  LNTYPE data) {
    MyNode *p = malloc(sizeof(MyNode));
    p->data = data;
    p->next = list->first;
    list->first = p;
    if(!list->last) list->last = p;
}

//插入第index个节点的前面
void myListInsertDataAt(MyList * const list, LNTYPE data, int index) {
    if(index == 0) {
        myListInsertDataAtFirst(list, data);
        return;
    }
    if(index == list->count) {
        myListInsertDataAtLast(list, data);
        return;
    }
    int i;
    MyNode *node = malloc(sizeof(MyNode));
    MyNode *p = list->first;
    node->data = data;
    for(i=0; i<index-1; i++)
        p = p->next;
    node->next = p->next;
    p->next = node;
}

//查找某个数据的位置,如果equal方法为空，比较地址，否则调用equal方法
//如果不存在返回-1，如果存在，返回出现的第一个位置
int myListFindDataIndex(const MyList * const list, LNTYPE data) {
    int i;
    MyNode *p = list->first;
    if(list->equal)
        for(i=0; p && !(*list->equal)(p->data, data); i++)
            p = p->next;
    else
         for(i=0; p && p->data != data; i++)
             p = p->next;
    if(i<list->count) return i;
    return -1;
}

//查找某个数据的位置,如果equal方法为空，则直接比较，否则调用equal方法
//如果不存在返回NULL，如果存在，否则返回查到的数据地址
//This is only for Set2Map
LNTYPE *myListFindDataAddr(const MyList * const list, LNTYPE data) {
    MyNode *p = list->first;
    if(list->equal)
        for(; p && !(*list->equal)(p->data, data); )
            p = p->next;
    else
         for(; p && p->data != data; )
             p = p->next;
    if(p) return &p->data;
    return NULL;
}

//取得数据
MyNode* myListGetDataAt(const MyList * const list, int index) {
    MyNode *p = list->first;
    while(index-- && p)
        p = p->next;
    return p;
}

//删除并返回尾部节点的数据
LNTYPE myListRemoveDataAtLast(MyList* const list) {
    MyNode *p = list->first;
    if(list->count == 1) {
        list->first = list->last = NULL;
    }else {
        while(p->next != list->last)
            p = p->next;
        list->last = p;
        p = p->next;
        list->last->next = NULL;
    }
    list->count--;
    LNTYPE data = p->data;
    free(p);
    return data;
}


//删除并返回首部节点的数据
LNTYPE myListRemoveDataAtFirst(MyList * const list) {
    if(list->count == 1)
        return myListRemoveDataAtLast(list);
    MyNode *p = list->first;
    list->first = list->first->next;
    list->count--;
    LNTYPE data = p->data;
    free(p);
    return data;
}

//创建遍历器,可直接free
MyListIterator* createMyListIterator(const MyList * const list) {
    MyListIterator *it = malloc(sizeof(MyListIterator));
    it->allSize = list->count;
    it->count = 0;
    it->p = list->first;
    return it;
}

//遍历器是否有下一个元素
int myListIteratorHasNext(const MyListIterator* const iterator) {
    return iterator->count < iterator->allSize;
}

//返回遍历器的下一个元素
LNTYPE myListIteratorNext(MyListIterator* const iterator) {
    MyNode *p = iterator->p;
    iterator->p = p->next;
    iterator->count++;
    return p->data;
}

int myListRemoveDataObject(MyList* const list, LNTYPE data) {
    MyNode *p, *pp;
    pp = p = list->first;
    if(list->equal) {
        while(p && !list->equal(p->data, data)) {
            pp = p;
            p = p->next;
        }     
    }else {
        while(p && p->data != data) {
            pp = p;
            p = p->next;
        }
    }
    if(p) {
        if(p == list->first) myListRemoveDataAtFirst(list);
        else {
            pp->next = p->next;
            if(p == list->last) list->last = pp;
            free(p);
        }
        return 1;
    }
    return 0;
}
